| 1. | (a) | The order of nodes of a Binary tree in Preorder and Inorder traversal are as under : |
| Preorder : A B D G H C E F I K
J Inorder : B G H D A E C I K F J Draw the corresponding Binary Tree. |
||
| (b) | Write a recursive algorithm to implement the following function | |
| n + 1, if m
= 0
A(m, n) = A (m-1, 1) , if n= 0 A(m - 1, A(m, n - 1 )), otherwise |
||
| (c) | convert the expression | |
| ((a + b) + c * (d + e) + f) * (g + h) to a postfix expression. | ||
| (d) | Write a 'C' function using pointers to return a substring of a string. The input to the program will be starting location and ending location of a substring in the input string. | |
| (e) | The following keys are to be inserted in the order shown into an AVL Tree: | |
| December, January, April, March,
July, August, October, February, September, November, May, June Show how the tree appears after each insertion. |
||
| 2. | (a) | Obtain a data representation that maps a stack and queue into a single array, memory [size]. |
| (b) | We must represent two stacks in an array memory [size]. Write PASCAL function that add and delete an item from stack stack_no, 0 <= stack_no <=1. Your functions should be able to add elements to the stacks as long as the total number of elements in both stacks is less than siz -1 | |
| 3. | (a) | What are the total number of nodes in a Binary tree of height k ? |
| (b) | Write a function that traverses a threaded Binary tree in post order. What are the time and space requirement of your method ? | |
| 4. | (a) | Find a Minimum Cost Spanning Tree of the following graph using Kruskal algorithm : |
 |
||
| (b) | Write Prim's Algorithm. | |
| 5. | Write a brief note on the following file organization techniques : | |
|
||
| Compare their storage and access efficiencies. To what type of applications are each of the techniques suited ? | ||
| 6. | (a) | Write an algorithm (recursive) to implement Merge Sort technique and discuss about its efficiency. |
| (b) | What are the advantages of Threaded Binary Trees over Binary Trees without threads ? | |
| (c) | What are the differences between Doubly Linked Lists and Singly Linked Lists ? |